home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Chip 1996 April
/
CHIP 1996 aprilis (CD06).zip
/
CHIP_CD06.ISO
/
hypertxt.arj
/
9301
/
THIBIT.CD
< prev
next >
Wrap
Text File
|
1995-04-18
|
14KB
|
289 lines
@VSzámok és bitek@N
@VA szeptemberi feladatokról@N
A Thibault-számok a következô feltételt elégítik ki: ha a
számot és négyzetét a 10-es számrendszerben felírjuk, akkor
minden 0-tól különbözô számjegyet pontosan egyszer, magát a
0-t egyszer sem használjuk fel. Ezeket számokat elôállító,
megkeresô programokat vártunk, és kaptunk is, méghozzá
nyolcat. A szokásos Pascal hegemóniát egy-egy Fortran
illetve Modula nyelvû program színesítette.
Célszerû némi matematikai megfontolással kezdenünk a
megoldást. Elemi eszközökkel pillanatok alatt
végiggondolható, hogy egy @KK@N jegyû szám négyzete
legalább @K2*K-1@N, de legfeljebb @K2*K@N jegyû lehet.
Mivel a számnak és négyzetének az 1, ..., 9 számjegyeket
pontosan egyszer kell tartalmaznia, ezért egy Thibault-szám
pontosan háromjegyû, négyzete pedig hatjegyû.
Azaz csak a négyzetgyök 100|000 (pontosabban négyzetgyök
123456 -- mivel ez a legkisebb különbözô jegyekbôl álló
szám -- ez körülbelül 352), és a 987 közé esô számokat kell
megvizsgálnunk (988-tól kezdve eleve vannak ismétlések).
A vizsgálandó kört természetesen tovább szûkíthetnénk,
hiszen például kiesnek azok a számok is amelyekben 0 van,
amelyek 1-re, 5-re, 6-ra végzôdnek, illetve ha az egyes
helyiértékû jegy megegyezik a tízes vagy a százas
helyiértékûvel stb. De kérdés, hogy érdemes-e ezeket a
feltételeket mind belepakolnunk egy olyan programba, amely
már az eddigiek alapján is alig több mint hatszáz
háromjegyû számot fog négyzetre emelni? A számjegyek
elôfordulása ellenôrizhetô volt karakterekké alakítva,
tömböt kezelve (a többség így járt el), de járható út --
megfelelô nyelvet választva -- az @K1000*N*N+N@N kifejezés
10-es maradékainak ismételt meghatározása, s az így kapott
számjegyekbôl álló halmaz vizsgálata (Szemenyei Bálint
ötlete). Magyarázatból elég ennyi. A közölt program Dudás
János lakonikus tömörségû munkája.
***** dudas.pas *****
[Dudás János, Debrecen
[CHIPkedd magad! CHIP IV.évf.9.szám Még mindig vannak számok... feladata.@N
program Thibault;
var s,s2:string;
c:char;
thib:boolean;
n:longint;
begin
for n:=round(sqrt(100000)) to 987 do
begin
thib:=true;
str(n:3,s); str(n*n:6,s2);
s:=s+s2;
for c:='1' to '9' do
thib:=thib and (pos(c,s)>0);
if thib then writeln('Thibault féle szám:',n:4,' és négyzete:',n*n:7);
end;
readln;
end.
a szerencse Kolozs András budapesti olvasónknak kedvezett,
egy doboz Tungsram floppy formájában. Na igen, az eredmény:
összesen kettô Thibault-szám van, az 567 és a 854.
A bitek falásáról szóló, Varga József által beküldött
feladat szövege a következô volt: tekintsünk egy
tetszôleges hosszúságú bitsorozatot. E sorozattal egy
dolgot tehetünk: az egymás mellett álló azonos bitek
kihúzhatók (egyszerre kettô vagy akár több is). Eldöntendô,
hogy ""elfogyasztható-e" a sorozat? E nehéz rejtvényre hat
megoldás érkezett, ebbôl öt Pascal nyelven készült (a
""kivételes" nyelv is családtag: a Modula).
Ez a nyelvi választás most indokoltnak tûnik. A probléma
szinte kiált a rekurzió alkalmazása után, ami ezeken a
nyelveken elég könnyen programozható. Megfejtôink egy része
(Déri Attila, Szemenyei Bálint, Tóth László) ezen az úton
indult el. Szemenyei Bálint dokumentációjából idézzük (ô
egyébként a Modulás kivétel) az alábbiakat:
""Egyszerû backtrack algoritmussal könnyen megoldhatjuk a
problémát.
*** mod.prn ***
RECURSIVE PROCEDURE Elfogyasztható( sorozat )
IF sorozat.hossza = 0 THEN
RETURN TRUE
ELSE
WHILE VanMégEhetôRész DO
új_sorozat:=sorozat - következô_ehetô_rész
IF Elfogyasztható( új_sorozat ) THEN
RETURN TRUE;
ENDIF
ENDWHILE
RETURN FALSE;
ENDIF
ENDPROC
A ""VanMégEhetôRész" azt adja meg, hogy az aktuális
sorozatban van-e még olyan, azonos bitekbôl álló, legalább
kettô hosszú sorozat, aminek az elfogyasztásával kapott új
sorozatot (az adott szinten) még nem vizsgáltuk. Ha van,
akkor kihúzzuk, és az így kapott új sorozatra rekurzívan
meghívva az eljárást próbáljuk meg eldönteni a problémát."
Az egyszerûség persze csak látszólagos, két szempontból is.
Egyfelôl az algoritmusban szereplô ""VanMégEhetôRész" és
""következô_ehetô_rész" nem születik meg csak úgy magától
-- nem teljesen triviális eljárások. Másrészt, mint
minden, rekurziót alkalmazó programnál, számolnunk kell egy
veszéllyel (amelyre olvasónk is utal), hogy tudniillik
nagyon sok egymásba ágyazott eljáráshívás, visszalépegetés
következik be (azaz megtelik a verem -- erre fôleg a
hosszabb, ""ehetetlen" sorozatoknál számíthatunk), s
programunk nemes egyszerûséggel kiakad.
Kis kitérô: a szó igazi értelmében ""tetszôleges"
hosszúságú bitsorozatot feldolgozó program nem írható,
ezért olvasóink többsége valamiféle ésszerû korlátot
állított fel, legtöbbször 255-ben maximálták -- részben a
fentiek, illetve a stringkezelés korlátai miatt -- a
bitspagetti hosszát. De például Verbôczi Zoltán programja
12|500 bit hosszúságú ""koszt" emésztésére is képes, persze
ennek megfelelô idô alatt. Bár éppen olvasónk mutatott
példát méretben és tartalomban alig különbözô olyan
sorozatokra, amelyek feldolgozási ideje százszorosan is
eltérhet, adott algoritmus esetén. Sajnáljuk, hogy érdekes
-- részben rekurzív, részben iteraktív -- programját
terjedelmi okokból nem tudjuk közölni.
Más módon közelített a problémához Horváth Sándor és Dudás
János. Megoldásukat a sorozat feldolgozhatóságával
kapcsolatos -- elôzôleg végiggondolt -- szabályokra
építették. Az alábbiakban Dudás János gondolatmenetét
próbáljuk meg vázolni.
Vegyük észre, hogy egy hosszabb egynemû részsorozatot nincs
értelme több lépésben ""elfogyasztani", hiszen ""szóló"
elemet gyártva csak rontunk a helyzeten, a sima
rövidítéssel pedig nem csináltunk semmit. Ez lehetôséget
teremt arra, hogy sorozatunkat átkódoljuk. Több egymás
mellett álló ""1" helyére írjunk ""E"-t, a szomszédos
""0"-kat egy ""N"-nel helyettesítjük (a szóló elemek
maradnak). îgy például a ""100101110" sorozatból ""1N10E0"
lesz. Világos, hogy a sorozat információtartalma nem
csökken, s például egy ""E" két oldalán vagy ""0", vagy
""N" lesz így. Ezzel az átkódolt sorozattal dolgozunk
tovább. Két eset lehetséges: a sorozat hossza páratlan,
vagy páros. Vizsgáljuk elôször a páratlan hosszú
sorozatokat. Itt három eset lehet:
1. A sorozat hossza 1. Ez csak akkor ""fogyasztható", ha az
elem ""E" vagy ""N", különben megfekszi gyomrunkat.
2. A sorozat közepén (páratlan hossz esetén ez értelmes)
""E" vagy ""N" van. Tessék meggondolni, hogy ez egyfajta
""középpontos típus-szimmetriát" jelent, azaz a középsô
elem törlésével indítva a sorozat eltüntethetô.
3. Ha középen nem betû ("E" vagy "N") áll, akkor azok
középre hozhatóságán múlik, hogy megoldható-e a feladat.
Szemléletesen: azon múlik, hogy nincs-e valamelyik a
""periférián", azaz a másikhoz képest nem helyezkedik-e túl
messze a centrumtól. Olvasónk ennek jellemzésére egyszerû
matematikai összefüggést talált: ha @Kb@N illetve @Kj@N
jelöli a középtôl balra illetve jobbra lévô elsô betû
pozícióját (a sorozat elejétôl számítva), akkor a középre
hozhatóság feltétele: @Kb+c>j@N alakba írható, ahol @Kc@N
a közép helye.
A páros hosszúságú sorozatot megpróbáljuk minden lehetséges
módon két páratlan hosszúra szétvágni, s közben az elôbb
tárgyalt módon megállapítani törölhetôségüket (célszerûen
egy függvényként megírva a fenti vizsgálatot, amely
igen/nem válasszal tér vissza, argumentumként a
részsorozatot várja). A teljes páros sorozat akkor
törölhetô, ha van olyan, páratlan hosszakra való
felbontása, amelyek külön-külön eltüntethetôk. Az
eljárásnak ez a másik, picit idôigényesebb része. Amúgy
felettébb gyors az algoritmus, hiszen csak egyszerû
számításokat végez (ráadásul a verem megtelésének a
veszélye sem fenyeget). A fenti három eljárást (átkódolás,
páratlanfogyaszthatóság, párosfogyaszthatóság) megírva a
feladat kérdésére válasz adható.
Mintaképpen Tóth László rekurziót alkalmazó programját
közöljük -- frappáns rövidségén túl azért is, mert
megvalósít egy, a feladatban nem szereplô plusz
szolgáltatást, tudniillik a törléseket, átalakításokat a
program regisztrálja, s a futás végén kiírja. îgy a
szabályszerûségek felismerhetôk, tanulmányozhatók. Mivel
rekurzív eljárásról van szó, futtatáskor érdemes --
különösen ha hosszabb sorozatokkal ""fárasztani" akarjuk a
programot -- a verem méretére, illetve a változók típusára
figyelni (integer helyett longint).
***** tothl.pas *****
program bitfalo;
[Tóth László
uses crt;
const s='101101101111000111101011001010';
var torolheto:boolean;
c:char;
t,tut:array[1..128,0..1 of byte;
j:integer;
s1:string;
procedure vizsgal(a:string;h,sz:byte);
var i,j,x,k:integer;
sor:array[1..128,0..1@N of byte;
c,d:char;
b:string;
azonos:boolean;
begin
if (torolheto) or (h=1) then exit;
sz:=sz+1;
c:=a[1;
azonos:=true;
for i:=2 to h do
if c<>a[i@N then azonos:=false;
if azonos then begin
torolheto:=true;
tut:=t;
end
else begin
for i:=1 to h do begin
sor[i,0:=0;
sor[i,1@N:=0;
end;
k:=0;
j:=1;
for i:=2 to h do
if c=a[i then if k=0 then begin
sor[j,0@N:=i-1;
k:=1;
sor[j,1:=2;
j:=j+1;
end
else sor[j-1,1@N:=sor[j-1,1+1
else begin
c:=a[i@N;
k:=0;
end;
if j>1 then for i:=1 to j-1 do begin
b:=a;
c:=b[sor[i,0@N;
t[sz,0:=sor[i,0@N;
t[sz,1:=sor[i,1@N;
delete(b,sor[i,0,sor[i,1@N);
vizsgal(b,length(b),sz);
end;
end
end;
BEGIN
clrscr;
torolheto:=false;
for j:=1 to 128 do begin
t[j,0:=0;
t[j,1@N:=0;
end;
tut:=t;
vizsgal(s,length(s),0);
if torolheto then begin
writeln('A ',s,' számsor letörölhetô,a következô módon: ');
s1:=s;
j:=1;
while tut[j,0<>0 do begin
delete(s1,tut[j,0@N,tut[j,1);
writeln(s1);
j:=j+1;
end;
end
else writeln('A ',s,' számsor nem törölhetô');
c:=readkey;
end.
@KBánhegyesi Zoltán@N